home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 10 / AACD 10.iso / AACD / Games / WarpQuake / Src / r_bsp.c < prev    next >
C/C++ Source or Header  |  2000-05-22  |  15KB  |  674 lines
  1. /*
  2. Copyright (C) 1996-1997 Id Software, Inc.
  3.  
  4. This program is free software; you can redistribute it and/or
  5. modify it under the terms of the GNU General Public License
  6. as published by the Free Software Foundation; either version 2
  7. of the License, or (at your option) any later version.
  8.  
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
  12.  
  13. See the GNU General Public License for more details.
  14.  
  15. You should have received a copy of the GNU General Public License
  16. along with this program; if not, write to the Free Software
  17. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18.  
  19. */
  20. // r_bsp.c
  21.  
  22. #include "quakedef.h"
  23. #include "r_local.h"
  24.  
  25. //
  26. // current entity info
  27. //
  28. qboolean        insubmodel;
  29. entity_t        *currententity;
  30. vec3_t            modelorg, base_modelorg;
  31.                                 // modelorg is the viewpoint reletive to
  32.                                 // the currently rendering entity
  33. vec3_t            r_entorigin;    // the currently rendering entity in world
  34.                                 // coordinates
  35.  
  36. static float            entity_rotation[3][3];
  37.  
  38. vec3_t            r_worldmodelorg;
  39.  
  40. int                r_currentbkey;
  41.  
  42. typedef enum {touchessolid, drawnode, nodrawnode} solidstate_t;
  43.  
  44. #define MAX_BMODEL_VERTS    500            // 6K
  45. #define MAX_BMODEL_EDGES    1000        // 12K
  46.  
  47. static mvertex_t    *pbverts;
  48. static bedge_t        *pbedges;
  49. static int            numbverts, numbedges;
  50.  
  51. static mvertex_t    *pfrontenter, *pfrontexit;
  52.  
  53. static qboolean        makeclippededge;
  54.  
  55. //===========================================================================
  56.  
  57. /*
  58. ================
  59. R_EntityRotate
  60. ================
  61. */
  62. void R_EntityRotate (vec3_t vec)
  63. {
  64.     vec3_t    tvec;
  65.  
  66.     VectorCopy (vec, tvec);
  67.     vec[0] = DotProduct (entity_rotation[0], tvec);
  68.     vec[1] = DotProduct (entity_rotation[1], tvec);
  69.     vec[2] = DotProduct (entity_rotation[2], tvec);
  70. }
  71.  
  72.  
  73. /*
  74. ================
  75. R_RotateBmodel
  76. ================
  77. */
  78. void R_RotateBmodel (void)
  79. {
  80.     float    angle, s, c, temp1[3][3], temp2[3][3], temp3[3][3];
  81.  
  82. // TODO: should use a look-up table
  83. // TODO: should really be stored with the entity instead of being reconstructed
  84. // TODO: could cache lazily, stored in the entity
  85. // TODO: share work with R_SetUpAliasTransform
  86.  
  87. // yaw
  88.     angle = currententity->angles[YAW];        
  89.     angle = angle * M_PI*2 / 360;
  90.     s = sin(angle);
  91.     c = cos(angle);
  92.  
  93.     temp1[0][0] = c;
  94.     temp1[0][1] = s;
  95.     temp1[0][2] = 0;
  96.     temp1[1][0] = -s;
  97.     temp1[1][1] = c;
  98.     temp1[1][2] = 0;
  99.     temp1[2][0] = 0;
  100.     temp1[2][1] = 0;
  101.     temp1[2][2] = 1;
  102.  
  103.  
  104. // pitch
  105.     angle = currententity->angles[PITCH];        
  106.     angle = angle * M_PI*2 / 360;
  107.     s = sin(angle);
  108.     c = cos(angle);
  109.  
  110.     temp2[0][0] = c;
  111.     temp2[0][1] = 0;
  112.     temp2[0][2] = -s;
  113.     temp2[1][0] = 0;
  114.     temp2[1][1] = 1;
  115.     temp2[1][2] = 0;
  116.     temp2[2][0] = s;
  117.     temp2[2][1] = 0;
  118.     temp2[2][2] = c;
  119.  
  120.     R_ConcatRotations (temp2, temp1, temp3);
  121.  
  122. // roll
  123.     angle = currententity->angles[ROLL];        
  124.     angle = angle * M_PI*2 / 360;
  125.     s = sin(angle);
  126.     c = cos(angle);
  127.  
  128.     temp1[0][0] = 1;
  129.     temp1[0][1] = 0;
  130.     temp1[0][2] = 0;
  131.     temp1[1][0] = 0;
  132.     temp1[1][1] = c;
  133.     temp1[1][2] = s;
  134.     temp1[2][0] = 0;
  135.     temp1[2][1] = -s;
  136.     temp1[2][2] = c;
  137.  
  138.     R_ConcatRotations (temp1, temp3, entity_rotation);
  139.  
  140. //
  141. // rotate modelorg and the transformation matrix
  142. //
  143.     R_EntityRotate (modelorg);
  144.     R_EntityRotate (vpn);
  145.     R_EntityRotate (vright);
  146.     R_EntityRotate (vup);
  147.  
  148.     R_TransformFrustum ();
  149. }
  150.  
  151.  
  152. /*
  153. ================
  154. R_RecursiveClipBPoly
  155. ================
  156. */
  157. void R_RecursiveClipBPoly (bedge_t *pedges, mnode_t *pnode, msurface_t *psurf)
  158. {
  159.     bedge_t        *psideedges[2], *pnextedge, *ptedge;
  160.     int            i, side, lastside;
  161.     float        dist, frac, lastdist;
  162.     mplane_t    *splitplane, tplane;
  163.     mvertex_t    *pvert, *plastvert, *ptvert;
  164.     mnode_t        *pn;
  165.  
  166.     psideedges[0] = psideedges[1] = NULL;
  167.  
  168.     makeclippededge = false;
  169.  
  170. // transform the BSP plane into model space
  171. // FIXME: cache these?
  172.     splitplane = pnode->plane;
  173.     tplane.dist = splitplane->dist -
  174.             DotProduct(r_entorigin, splitplane->normal);
  175.     tplane.normal[0] = DotProduct (entity_rotation[0], splitplane->normal);
  176.     tplane.normal[1] = DotProduct (entity_rotation[1], splitplane->normal);
  177.     tplane.normal[2] = DotProduct (entity_rotation[2], splitplane->normal);
  178.  
  179. // clip edges to BSP plane
  180.     for ( ; pedges ; pedges = pnextedge)
  181.     {
  182.         pnextedge = pedges->pnext;
  183.  
  184.     // set the status for the last point as the previous point
  185.     // FIXME: cache this stuff somehow?
  186.         plastvert = pedges->v[0];
  187.         lastdist = DotProduct (plastvert->position, tplane.normal) -
  188.                    tplane.dist;
  189.  
  190.         if (lastdist > 0)
  191.             lastside = 0;
  192.         else
  193.             lastside = 1;
  194.  
  195.         pvert = pedges->v[1];
  196.  
  197.         dist = DotProduct (pvert->position, tplane.normal) - tplane.dist;
  198.  
  199.         if (dist > 0)
  200.             side = 0;
  201.         else
  202.             side = 1;
  203.  
  204.         if (side != lastside)
  205.         {
  206.         // clipped
  207.             if (numbverts >= MAX_BMODEL_VERTS)
  208.                 return;
  209.  
  210.         // generate the clipped vertex
  211.             frac = lastdist / (lastdist - dist);
  212.             ptvert = &pbverts[numbverts++];
  213.             ptvert->position[0] = plastvert->position[0] +
  214.                     frac * (pvert->position[0] -
  215.                     plastvert->position[0]);
  216.             ptvert->position[1] = plastvert->position[1] +
  217.                     frac * (pvert->position[1] -
  218.                     plastvert->position[1]);
  219.             ptvert->position[2] = plastvert->position[2] +
  220.                     frac * (pvert->position[2] -
  221.                     plastvert->position[2]);
  222.  
  223.         // split into two edges, one on each side, and remember entering
  224.         // and exiting points
  225.         // FIXME: share the clip edge by having a winding direction flag?
  226.             if (numbedges >= (MAX_BMODEL_EDGES - 1))
  227.             {
  228.                 Con_Printf ("Out of edges for bmodel\n");
  229.                 return;
  230.             }
  231.  
  232.             ptedge = &pbedges[numbedges];
  233.             ptedge->pnext = psideedges[lastside];
  234.             psideedges[lastside] = ptedge;
  235.             ptedge->v[0] = plastvert;
  236.             ptedge->v[1] = ptvert;
  237.  
  238.             ptedge = &pbedges[numbedges + 1];
  239.             ptedge->pnext = psideedges[side];
  240.             psideedges[side] = ptedge;
  241.             ptedge->v[0] = ptvert;
  242.             ptedge->v[1] = pvert;
  243.  
  244.             numbedges += 2;
  245.  
  246.             if (side == 0)
  247.             {
  248.             // entering for front, exiting for back
  249.                 pfrontenter = ptvert;
  250.                 makeclippededge = true;
  251.             }
  252.             else
  253.             {
  254.                 pfrontexit = ptvert;
  255.                 makeclippededge = true;
  256.             }
  257.         }
  258.         else
  259.         {
  260.         // add the edge to the appropriate side
  261.             pedges->pnext = psideedges[side];
  262.             psideedges[side] = pedges;
  263.         }
  264.     }
  265.  
  266. // if anything was clipped, reconstitute and add the edges along the clip
  267. // plane to both sides (but in opposite directions)
  268.     if (makeclippededge)
  269.     {
  270.         if (numbedges >= (MAX_BMODEL_EDGES - 2))
  271.         {
  272.             Con_Printf ("Out of edges for bmodel\n");
  273.             return;
  274.         }
  275.  
  276.         ptedge = &pbedges[numbedges];
  277.         ptedge->pnext = psideedges[0];
  278.         psideedges[0] = ptedge;
  279.         ptedge->v[0] = pfrontexit;
  280.         ptedge->v[1] = pfrontenter;
  281.  
  282.         ptedge = &pbedges[numbedges + 1];
  283.         ptedge->pnext = psideedges[1];
  284.         psideedges[1] = ptedge;
  285.         ptedge->v[0] = pfrontenter;
  286.         ptedge->v[1] = pfrontexit;
  287.  
  288.         numbedges += 2;
  289.     }
  290.  
  291. // draw or recurse further
  292.     for (i=0 ; i<2 ; i++)
  293.     {
  294.         if (psideedges[i])
  295.         {
  296.         // draw if we've reached a non-solid leaf, done if all that's left is a
  297.         // solid leaf, and continue down the tree if it's not a leaf
  298.             pn = pnode->children[i];
  299.  
  300.         // we're done with this branch if the node or leaf isn't in the PVS
  301.             if (pn->visframe == r_visframecount)
  302.             {
  303.                 if (pn->contents < 0)
  304.                 {
  305.                     if (pn->contents != CONTENTS_SOLID)
  306.                     {
  307.                         r_currentbkey = ((mleaf_t *)pn)->key;
  308.                         R_RenderBmodelFace (psideedges[i], psurf);
  309.                     }
  310.                 }
  311.                 else
  312.                 {
  313.                     R_RecursiveClipBPoly (psideedges[i], pnode->children[i],
  314.                                       psurf);
  315.                 }
  316.             }
  317.         }
  318.     }
  319. }
  320.  
  321.  
  322. /*
  323. ================
  324. R_DrawSolidClippedSubmodelPolygons
  325. ================
  326. */
  327. void R_DrawSolidClippedSubmodelPolygo (model_t *pmodel)
  328. {
  329.     int            i, j, lindex;
  330.     vec_t        dot;
  331.     msurface_t    *psurf;
  332.     int            numsurfaces;
  333.     mplane_t    *pplane;
  334.     mvertex_t    bverts[MAX_BMODEL_VERTS];
  335.     bedge_t        bedges[MAX_BMODEL_EDGES], *pbedge;
  336.     medge_t        *pedge, *pedges;
  337.  
  338. // FIXME: use bounding-box-based frustum clipping info?
  339.  
  340.     psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
  341.     numsurfaces = pmodel->nummodelsurfaces;
  342.     pedges = pmodel->edges;
  343.  
  344.     for (i=0 ; i<numsurfaces ; i++, psurf++)
  345.     {
  346.     // find which side of the node we are on
  347.         pplane = psurf->plane;
  348.  
  349.         dot = DotProduct (modelorg, pplane->normal) - pplane->dist;
  350.  
  351.     // draw the polygon
  352.         if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
  353.             (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
  354.         {
  355.         // FIXME: use bounding-box-based frustum clipping info?
  356.  
  357.         // copy the edges to bedges, flipping if necessary so always
  358.         // clockwise winding
  359.         // FIXME: if edges and vertices get caches, these assignments must move
  360.         // outside the loop, and overflow checking must be done here
  361.             pbverts = bverts;
  362.             pbedges = bedges;
  363.             numbverts = numbedges = 0;
  364.  
  365.             if (psurf->numedges > 0)
  366.             {
  367.                 pbedge = &bedges[numbedges];
  368.                 numbedges += psurf->numedges;
  369.  
  370.                 for (j=0 ; j<psurf->numedges ; j++)
  371.                 {
  372.                    lindex = pmodel->surfedges[psurf->firstedge+j];
  373.  
  374.                     if (lindex > 0)
  375.                     {
  376.                         pedge = &pedges[lindex];
  377.                         pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[0]];
  378.                         pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[1]];
  379.                     }
  380.                     else
  381.                     {
  382.                         lindex = -lindex;
  383.                         pedge = &pedges[lindex];
  384.                         pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[1]];
  385.                         pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[0]];
  386.                     }
  387.  
  388.                     pbedge[j].pnext = &pbedge[j+1];
  389.                 }
  390.  
  391.                 pbedge[j-1].pnext = NULL;    // mark end of edges
  392.  
  393.                 R_RecursiveClipBPoly (pbedge, currententity->topnode, psurf);
  394.             }
  395.             else
  396.             {
  397.                 Sys_Error ("no edges in bmodel");
  398.             }
  399.         }
  400.     }
  401. }
  402.  
  403.  
  404. /*
  405. ================
  406. R_DrawSubmodelPolygons
  407. ================
  408. */
  409. void R_DrawSubmodelPolygons (model_t *pmodel, int clipflags)
  410. {
  411.     int            i;
  412.     vec_t        dot;
  413.     msurface_t    *psurf;
  414.     int            numsurfaces;
  415.     mplane_t    *pplane;
  416.  
  417. // FIXME: use bounding-box-based frustum clipping info?
  418.  
  419.     psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
  420.     numsurfaces = pmodel->nummodelsurfaces;
  421.  
  422.     for (i=0 ; i<numsurfaces ; i++, psurf++)
  423.     {
  424.     // find which side of the node we are on
  425.         pplane = psurf->plane;
  426.  
  427.         dot = DotProduct (modelorg, pplane->normal) - pplane->dist;
  428.  
  429.     // draw the polygon
  430.         if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
  431.             (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
  432.         {
  433.             r_currentkey = ((mleaf_t *)currententity->topnode)->key;
  434.  
  435.         // FIXME: use bounding-box-based frustum clipping info?
  436.             R_RenderFace (psurf, clipflags);
  437.         }
  438.     }
  439. }
  440.  
  441.  
  442. /*
  443. ================
  444. R_RecursiveWorldNode
  445. ================
  446. */
  447. void R_RecursiveWorldNode (mnode_t *node, int clipflags)
  448. {
  449.     int            i, c, side, *pindex;
  450.     vec3_t        acceptpt, rejectpt;
  451.     mplane_t    *plane;
  452.     msurface_t    *surf, **mark;
  453.     mleaf_t        *pleaf;
  454.     double        d, dot;
  455.  
  456.     if (node->contents == CONTENTS_SOLID)
  457.         return;        // solid
  458.  
  459.     if (node->visframe != r_visframecount)
  460.         return;
  461.  
  462. // cull the clipping planes if not trivial accept
  463. // FIXME: the compiler is doing a lousy job of optimizing here; it could be
  464. //  twice as fast in ASM
  465.     if (clipflags)
  466.     {
  467.         for (i=0 ; i<4 ; i++)
  468.         {
  469.             if (! (clipflags & (1<<i)) )
  470.                 continue;    // don't need to clip against it
  471.  
  472.         // generate accept and reject points
  473.         // FIXME: do with fast look-ups or integer tests based on the sign bit
  474.         // of the floating point values
  475.  
  476.             pindex = pfrustum_indexes[i];
  477.  
  478.             rejectpt[0] = (float)node->minmaxs[pindex[0]];
  479.             rejectpt[1] = (float)node->minmaxs[pindex[1]];
  480.             rejectpt[2] = (float)node->minmaxs[pindex[2]];
  481.             
  482.             d = DotProduct (rejectpt, view_clipplanes[i].normal);
  483.             d -= view_clipplanes[i].dist;
  484.  
  485.             if (d <= 0)
  486.                 return;
  487.  
  488.             acceptpt[0] = (float)node->minmaxs[pindex[3+0]];
  489.             acceptpt[1] = (float)node->minmaxs[pindex[3+1]];
  490.             acceptpt[2] = (float)node->minmaxs[pindex[3+2]];
  491.  
  492.             d = DotProduct (acceptpt, view_clipplanes[i].normal);
  493.             d -= view_clipplanes[i].dist;
  494.  
  495.             if (d >= 0)
  496.                 clipflags &= ~(1<<i);    // node is entirely on screen
  497.         }
  498.     }
  499.     
  500. // if a leaf node, draw stuff
  501.     if (node->contents < 0)
  502.     {
  503.         pleaf = (mleaf_t *)node;
  504.  
  505.         mark = pleaf->firstmarksurface;
  506.         c = pleaf->nummarksurfaces;
  507.  
  508.         if (c)
  509.         {
  510.             do
  511.             {
  512.                 (*mark)->visframe = r_framecount;
  513.                 mark++;
  514.             } while (--c);
  515.         }
  516.  
  517.     // deal with model fragments in this leaf
  518.         if (pleaf->efrags)
  519.         {
  520.             R_StoreEfrags (&pleaf->efrags);
  521.         }
  522.  
  523.         pleaf->key = r_currentkey;
  524.         r_currentkey++;        // all bmodels in a leaf share the same key
  525.     }
  526.     else
  527.     {
  528.     // node is just a decision point, so go down the apropriate sides
  529.  
  530.     // find which side of the node we are on
  531.         plane = node->plane;
  532.  
  533.         switch (plane->type)
  534.         {
  535.         case PLANE_X:
  536.             dot = modelorg[0] - plane->dist;
  537.             break;
  538.         case PLANE_Y:
  539.             dot = modelorg[1] - plane->dist;
  540.             break;
  541.         case PLANE_Z:
  542.             dot = modelorg[2] - plane->dist;
  543.             break;
  544.         default:
  545.             dot = DotProduct (modelorg, plane->normal) - plane->dist;
  546.             break;
  547.         }
  548.     
  549.         if (dot >= 0)
  550.             side = 0;
  551.         else
  552.             side = 1;
  553.  
  554.     // recurse down the children, front side first
  555.         R_RecursiveWorldNode (node->children[side], clipflags);
  556.  
  557.     // draw stuff
  558.         c = node->numsurfaces;
  559.  
  560.         if (c)
  561.         {
  562.             surf = cl.worldmodel->surfaces + node->firstsurface;
  563.  
  564.             if (dot < -BACKFACE_EPSILON)
  565.             {
  566.                 do
  567.                 {
  568.                     if ((surf->flags & SURF_PLANEBACK) &&
  569.                         (surf->visframe == r_framecount))
  570.                     {
  571.                         if (r_drawpolys)
  572.                         {
  573.                             if (r_worldpolysbacktofront)
  574.                             {
  575.                                 if (numbtofpolys < MAX_BTOFPOLYS)
  576.                                 {
  577.                                     pbtofpolys[numbtofpolys].clipflags =
  578.                                             clipflags;
  579.                                     pbtofpolys[numbtofpolys].psurf = surf;
  580.                                     numbtofpolys++;
  581.                                 }
  582.                             }
  583.                             else
  584.                             {
  585.                                 R_RenderPoly (surf, clipflags);
  586.                             }
  587.                         }
  588.                         else
  589.                         {
  590.                             R_RenderFace (surf, clipflags);
  591.                         }
  592.                     }
  593.  
  594.                     surf++;
  595.                 } while (--c);
  596.             }
  597.             else if (dot > BACKFACE_EPSILON)
  598.             {
  599.                 do
  600.                 {
  601.                     if (!(surf->flags & SURF_PLANEBACK) &&
  602.                         (surf->visframe == r_framecount))
  603.                     {
  604.                         if (r_drawpolys)
  605.                         {
  606.                             if (r_worldpolysbacktofront)
  607.                             {
  608.                                 if (numbtofpolys < MAX_BTOFPOLYS)
  609.                                 {
  610.                                     pbtofpolys[numbtofpolys].clipflags =
  611.                                             clipflags;
  612.                                     pbtofpolys[numbtofpolys].psurf = surf;
  613.                                     numbtofpolys++;
  614.                                 }
  615.                             }
  616.                             else
  617.                             {
  618.                                 R_RenderPoly (surf, clipflags);
  619.                             }
  620.                         }
  621.                         else
  622.                         {
  623.                             R_RenderFace (surf, clipflags);
  624.                         }
  625.                     }
  626.  
  627.                     surf++;
  628.                 } while (--c);
  629.             }
  630.  
  631.         // all surfaces on the same node share the same sequence number
  632.             r_currentkey++;
  633.         }
  634.  
  635.     // recurse down the back side
  636.         R_RecursiveWorldNode (node->children[!side], clipflags);
  637.     }
  638. }
  639.  
  640.  
  641.  
  642. /*
  643. ================
  644. R_RenderWorld
  645. ================
  646. */
  647. void R_RenderWorld (void)
  648. {
  649.     int            i;
  650.     model_t        *clmodel;
  651.     btofpoly_t    btofpolys[MAX_BTOFPOLYS];
  652.  
  653.     pbtofpolys = btofpolys;
  654.  
  655.     currententity = &cl_entities[0];
  656.     VectorCopy (r_origin, modelorg);
  657.     clmodel = currententity->model;
  658.     r_pcurrentvertbase = clmodel->vertexes;
  659.  
  660.     R_RecursiveWorldNode (clmodel->nodes, 15);
  661.  
  662. // if the driver wants the polygons back to front, play the visible ones back
  663. // in that order
  664.     if (r_worldpolysbacktofront)
  665.     {
  666.         for (i=numbtofpolys-1 ; i>=0 ; i--)
  667.         {
  668.             R_RenderPoly (btofpolys[i].psurf, btofpolys[i].clipflags);
  669.         }
  670.     }
  671. }
  672.  
  673.  
  674.